奇點無限的A.I.R與google maps有何不同？3

各種VRP模型

VRP比較符合物流業現實主要是因為這個模型描述了多輛貨車的情境，而且可以再依業種不同修改成不同的數學模型，以下舉幾個常見的變形：

C: Capacitated 意指要考慮貨車容量限制(這個超基本的對吧！)

TW: Time Window 意指要考慮收貨者有沒有指定時間，也就是前文的時效性

PD: Pick-up Delivery 我都翻成邊揀邊送。這個形式又有好多變形，像是逆物流，或是食物快遞

B: Backhaul 回頭車

MD: Multi-Depot 現實中一家公司可能不只一個倉庫

那麼google maps完全無法符合第一線的物流需求嗎？這樣講也太嚴苛，如果我來回答，我會說：要付出極大代價。

解算VRP第一步-產生距離矩陣

有操作過VRP的人一定知道，在解算VRP家族問題時，我們要先產生距離矩陣。在數學中, 一個距離矩陣是一個各項元素為點之間距離的矩陣（二維數組）。因此給定N個歐幾里得空間中的點，其距離矩陣就是一個非負實數作為元素的N×N的對稱矩陣距離矩陣和鄰接矩陣概念相似，其區別在於後者僅包含元素（點）之間是否有連邊，並沒有包含元素（點）之間的連通的距離的訊息。因此，距離矩陣可以看成是鄰接矩陣的加權形式(維基百科)。

這一個矩陣的產生要花費極大的成本，以上面這張表的例子(可以假設物流公司要從a點出發去送貨到b,c,d,e,f點)，要計算20次點到點的最短路徑距離(扣掉對角線)。在點數少的時候，計算成本小，以經典的Dijkstra演算時，約台北市大小的路網，一對起訖的最短路徑演算(就是上表的一格)只需20ms，上述的距離矩陣大約400ms就可以算完，再進入VRP的演算。(這裡不考慮使用曼哈頓距離以加速計算)

但是以前文提到一輛3.5頓的堅達一天送100個地址，那麼這個距離矩陣就會有9,900個最短路徑距離要計算，就要花掉9900x20ms=198秒，才能進入VRP的演算。

光計算距離矩陣就要花掉3分多鐘，更遑論進入複雜的VRP模型找答案了。

其實Google maps有提供一個API就在做距離矩陣運算的，但這個成本非常高，以官網的報價來看，基本定價是一對起訖的最短距離計算要價0.01美金。

以上表的規模，計算距離矩陣要花費20x0.01=2美金，如果你對這個數字沒感覺，以3.5頓堅達的100個地址來看，就要花9900x0.01=99美金？！然後還不能幫你做最佳路線計算！你要自己寫出可以解算VRP的程式！！

奇點無限的A.I.R與google maps在物流應用的比較